package com.code.leetcode.offer;

import com.code.leetcode.offer.utils.*;

import java.io.Serializable;

/**
 * @author codeDorado
 * @version 1.0
 * @date 2020/8/1 20:54
 */
public class The35 {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        copyNode(head);
        change(head);
        return getNewLinked(head);
    }

    public void copyNode(Node head) {
        while (head != null) {
            Node clone = new Node(head.val);
            clone.next = head.next;
            head.next = clone;
            head = clone.next;
        }
    }

    public void change(Node head) {
        while (head != null) {
            Node clone = head.next;
            if (head.random != null) {
                clone.random = head.random.next;
            }
            head = clone.next;
        }
    }

    // 利用第一步将 head 放到 clone 的后面
    public Node getNewLinked(Node head) {
        Node cloneHead = head.next;
        Node clone = head.next;
        head.next = clone.next;
        head = head.next;
        while (head != null) {
            clone.next = head.next;
            head.next = head.next.next;
            head = head.next;
            clone = clone.next;
        }
        return cloneHead;
    }

}
